BZOJ 1002 轮状病毒

Description

给定n(N<=100),编程计算有多少个不同的n轮状病毒。

Input

第一行有1个正整数n。

Output

将编程计算出的不同的n轮状病毒数输出

Sample Input

3

Sample Output

16

Solution

第一眼看到以为是生成树计数
打了个Matrix-Tree
惊喜的发现要高精度
然后偷偷去看了一下题解
发现有规律0.0
然后就愉快地打递推了
其实找规律应该就可以了吧

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>

#define maxn 100+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

int f[maxn][maxn],len[maxn];
int n;

void get(int x)
{

len[x]=len[x-1];
for(int i=1;i<=len[x];i++)
f[x][i]=f[x-1][i];
for(int i=1;i<=len[x];i++)
f[x][i]*=3;
f[x][1]+=2;
for(int i=1;i<=len[x];i++)
if( f[x][i]>=10 ){
f[x][i+1]+=f[x][i]/10;
f[x][i]%=10;
if( i==len[x] ) len[x]++;
}
for(int i=1;i<=len[x-2];i++)
f[x][i]-=f[x-2][i];
for(int i=1;i<=len[x];i++)
if( f[x][i]<0 ){
f[x][i+1]--;
f[x][i]+=10;
}
while( !f[x][len[x]] ) len[x]--;
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("1002.in","r",stdin);
freopen("1002.out","w",stdout);
#endif
scanf("%d",&n);
f[1][1]=1,len[1]=1;
for(int i=2;i<=n;i++)
get(i);
for(int i=len[n];i>=1;i--)
printf("%d",f[n][i]);
return 0;
}